package greedy

// 与45号算法题 跳跃游戏II差不多， 找到每步最远能跳
// 如果最远都到不了，那就到不了了, 只有碰到0的时候才会跳不走
func canJump(nums []int) bool {
	n := len(nums)
	// 初始化跳跃的范围，用双指针表示，start表示当前位置
	// end 表示当前点能跳到的最远位置
	start := 0
	end := start + nums[start]
	// 只要end可以指到最后一个位置，就能到
	for end < n-1 {
		// start == end 说明当前走到了节点为 0 的位置了！返回错误
		if start == end {
			return false
		}
		// 找到下一个最优的跳跃点
		for i := start; i <= end; i++ {
			if max(i+nums[i], start+nums[start]) {
				start = i
			}
		}
		// 更新start，end
		// 正常情况下，end 应该更新到 新的start + nums[start] 新的点的最远跳点
		// 只要不是零值，一般来讲 start  应该更新到上一个跳点的 end 位置，因为 新start 到 老 end位置都测试过了,避免重复算
		temp := start
		start = end
		end = temp + nums[temp]
	}
	return true
}

func max(a, b int) bool {
	if a > b {
		return true
	}
	return false
}

// 更简单的写法，可以知道，碰到0就不行了，到不了了。
// 那么我们只需要顺序遍历每一个位置，一直求得遍历过的这些元素所能到的最远位置。
// 当最远位置 小于了当前的遍历的位置，说明停滞不前了！碰到 0 了
func canJump(nums []int) bool {
	n := len(nums)
	maxPos := 0
	for i := 0; i < n; i++ {
		if maxPos < i {
			return false
		}
		// 1. 计算到当前位置，能跳的最远位置
		maxPos = max(maxPos, i+nums[i])
	}
	return true
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
